package solution;

import java.util.*;

/**
 * DirectedCycle.java
 * @param <V>
 * ---------------------------------------------------------------------------------------
 *
 * Directed cycle detection.
 *
 * Does a given digraph have a directed cycle?
 * - If so, find the vertices on some such cycle, in order from some vertex back to itself.
 *
 *
 */
public class DirectedCycle<V> {
    private Set<V> marked;

    private Map<V, V> edgeTo;

    private Set<V> onStack;

    private Deque<V> cycle;

    public DirectedCycle(Graph<V> graph) {
        this.marked = new HashSet<>();
        this.edgeTo = new HashMap<>();
        this.onStack = new HashSet<>();

        for (V v : graph.vertices()) {
            if (!marked.contains(v)) {
                dfs(graph, v);
            }
        }
    }

    private void dfs(Graph<V> graph, V v) {
        marked.add(v);
        onStack.add(v);

        for (Edge<V> edge : graph.neighbors(v)) {
            V w = edge.getTo();
            if (this.hasCycle()) {
                return;
            }

            if (!marked.contains(w)) {
                edgeTo.put(w, v);
                dfs(graph, w);
            }else if (onStack.contains(w)) {
                cycle = new ArrayDeque<>();
                for (V x = v; x != w; x = edgeTo.get(x)) {
                    cycle.push(x);
                }
                cycle.push(w);
                cycle.push(v);
            }
        }

        onStack.remove(v);

    }

    public boolean hasCycle(){
        return cycle != null;
    }

    public Iterable<V> cycle(){
        return cycle;
    }
}
